/*************************************************************************
	> File Name: 2552.cpp
	> Author: yufangze
	> Mail: 2224590123@qq.com
	> Created Time: 2025-02-24 16:35:34
 ************************************************************************/

class Solution {
public:
    long long countQuadruplets(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> great(n, vector<int>(n + 1));
        vector<vector<int>> less(n, vector<int>(n + 1));
        // great
        for (int k = n - 2; k >= 2; k--) {
            for (int x = 1; x <= n; x++) {
                if (x < nums[k + 1]) {
                    great[k][x] = great[k + 1][x] + 1;
                } else {
                    great[k][x] = great[k + 1][x];
                }
            }
        }
        // less
        for (int j = 1; j < n - 2; j++) {
            for (int x = 1; x <= n; x++) {
                if (x > nums[j - 1]) {
                    less[j][x] = less[j - 1][x] + 1;
                } else {
                    less[j][x] = less[j - 1][x];
                }
            }
        }
        long long ans = 0;
        for (int j = 1; j < n - 2; j++) {
            for (int k = j + 1; k < n - 1; k++) {
                if (nums[j] > nums[k]) {
                    ans += less[j][nums[k]] * great[k][nums[j]];
                }
            }
        }
        return ans;
    }
};
